package com.zyf;

import java.util.Scanner;

/**
 * 5 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引,如果目标值不存在数组中,返回他将会被按顺序插入的位置
你可以假设数组中无重复元素

示例 1 
输入 :  {1,3,5,6} , 5
输出 :  2
示例 2 
输入 :  {1,3,5,6} , 4
输出 :  2

 * @author lenovo
 * @Date 2020年7月2日
 * @Time 下午3:09:09
 */
public class _05_insertionLocation {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		System.out.println("输入一个数组长度 : " );
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		System.out.println("输入一个长度为 " + n +"的排序数组 : " );
		for (int i = 0; i < arr1.length; i++) {
			arr1[i] = sc.nextInt();
		}
		System.out.println("输入要插入的值 : " );
		int m = sc.nextInt();
		int m1 = insertion(arr1,m);
		System.out.println("索引位置 : " + m1);
	}
	/**
	 * 搜索插入位置方法
	 * @param arr1
	 * @param m
	 * @return 元素下标索引n
	 * 
	 * 思路:
	 * 遍历arr1,判断 m 的值和数组元素的大小关系
	 * 分四种情况:
	 *	 	1 数组中存在 m 的值,返回数组下标
	 * 		2 不存在 m 的值,找到一个 arr1[i] 小于 m 的值,同时 arr1[i+1] 大于 m ,返回i+1
	 * 		3 m 的值小于数组的第一个元素,返回0
	 * 		4 m 的值大于数组的最后一个元素,返回数组最后一个位置
	 * 
	 * 优化:
	 * 
	 * 因为数组 arr1[] 中的元素是排好序的,从小到大
	 * 从左往右依次遍历,并与m的值比较,大于等于 m 说明就是数据下标
	 * 若全部遍历完毕没有数据 
	 * 则返回数组的最大值
	 */
	public static int insertion(int[] arr1, int m) {
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] >= m) {
				//方法遇 return 结束,一旦找到符合要求的下标,就结束方法 
				return i;
			}
		}
		//到这里说明没有执行方法中的 return
		//数据比数组中的任意一个值都大,插入到数组最后位置,返回数组长度就是下标
		return arr1.length;
	}

}
